---

Overview

Find Divisors / Integer Factorization Problem

$N$ is a sum of $k$ consecutive numbers, i.e. $N = (x + 1) + (x + 2) + ... + (x + k)$.

Let's regroup the terms $N = x k + (1 + 2 + ... + k)$ and use well-known formula for the sum of natural numbers $1 + 2 + ... + k = \frac{k(k + 1)}{2}$:

$N = x k + \frac{k (k + 1)}{2} \qquad (1)$

$2N = k (2x + k + 1) \qquad (2)$

That means, the problem is to figure out all possible pairs of $k$ and $2x + k + 1$ which are both divisors of a number $2N$. To find a number of ways to factor $2N$ is the so-called Integer Factorisation problem.

The best way to solve this problem is to run Shor's Algorithm on the quantum computer, that requires $\mathcal{O}(\log^2 N \log \log N \log \log \log N)$ time. If there is no quantum computer in the interview room, just use classical GNFS Algorithm, which runs in a decent $\mathcal{O}(e^{\log^{1/3} N (\log \log N)^{2/3}})$ time.

Speaking seriously, one has to stay reasonable during the interview and figure out the right balance between speed and simplicity.

Time Complexity to Target During the Interview: $\mathcal{O}(\sqrt{N})$

First, one could iterate from $1$ to $N$ and figure out all divisors in a linear time.

Second, the divisors are paired, i.e. if number $i$ is a divisor of $N$, then number $N / i$ is a divisor of $N$ too. That means it's enough to iterate up to $\sqrt{N}$.

$\mathcal{O}(\sqrt{N})$ is definitely enough for the interview. In this article, we consider two simple solutions, which are good suite for the interview and keep the rest out of scope.

---

Approach 1: Mathematical: Sum of First $k$ Natural Numbers, $\mathcal{O}(\sqrt{N})$ time

Intuition

Let's use the formula we derived above

$N = x k + \frac{k (k + 1)}{2} \qquad (1)$

derive $x$

$x = \frac{N}{k} - \frac{k + 1}{2} \qquad (3)$

and set two constraints:

• $x$ should be greater or equal to zero.

• $x$ should be an integer.

The first constraint is easy to apply using completing the square technique

$\frac{N}{k} \ge \frac{k + 1}{2} \qquad (4)$

$2N + \frac{1}{4} \ge \left(k + \frac{1}{2}\right)^2 \qquad (5)$

$k \le \sqrt{2N + \frac{1}{4}} - \frac{1}{2} \qquad (6)$

The first constraint sets the upper boundary for $k$. The second constraint, $x$ should be an integer, can be verified during the iteration over $k$.

Algorithm

• Initiate the counter to zero.

• Iterate over $k$ from $1$ to $\sqrt{2N + \frac{1}{4}} - \frac{1}{2}$.

• If $x = \frac{N}{k} - \frac{k + 1}{2}$ is an integer, increase the counter by one.

• Return the counter.

Implementation

Complexity Analysis

• Time Complexity: $\mathcal{O}(\sqrt{N})$.

• Space Complexity: $O(1)$.
  
  

---

Approach 2: Mathematical: Decrease $N$ Gradually, $\mathcal{O}(\sqrt{N})$ time

Intuition

Now let's optimize Approach 1. The idea is to use the same iteration limits for $k$, and to decrease $N$ by $k$ at each step.

At each step, we check if $N$ can be composed by the sum of $k$ consecutive numbers, i.e. $N = (x + 1) + (x + 2) + ... + (x + k) = xk + (1 + 2 + ... + k)$.

By removing all the complementary terms (1, 2, ... k) one by one, we reduce the number $N$ from $xk + (1 + 2 + ... + k)$ down to $N = x k$. Since $x$ should be an integer, $k$ should be a divisor of $N$, i.e. N % k == 0.

Algorithm

• Initiate the counter to zero.

• Iterate over $k$ from $1$ to $\sqrt{2N + \frac{1}{4}} - \frac{1}{2}$.

• Decrease $N$ by $k$, to keep $x k$ term only.

• Verify that $x$ is an integer: N % k == 0. If it's the case, increase the counter by one.

• Return the counter.

Implementation

Complexity Analysis

• Time Complexity: $\mathcal{O}(\sqrt{N})$.

• Space Complexity: $O(1)$.
  
  

---

class Solution:
    def consecutiveNumbersSum(self, N: int) -> int:
        
        constant_term = 0
        divisor = 1
        ans = 0
        while constant_term < N:
            if ((N-constant_term)/divisor).is_integer():
                ans += 1
            
            constant_term = constant_term + divisor
            divisor += 1
        
        return ans
        

def consecutiveNumbersSum(self, N):
    count = 0
    for i in range(1, int(math.sqrt(N))+1):
        if N%i == 0:
            if i%2:
                count += 1
            if (N/i)%2 and N/i != i:
                count += 1
    return count